#define _CRT_SECURE_NO_WARNINGS 1
const int N = 1e6 + 10;
bool st[N] = { 0 };
int prim[N] = { 0 };
int cnt = 0;

void getprim() {
    st[0] = st[1] = true;
    for (int i = 2; i < N; i++) {
        if (!st[i])prim[cnt++] = i;
        for (int j = 0; i < N / prim[j]; j++) {
            st[prim[j] * i] = true;
            if (i % prim[j] == 0)break;
        }
    }
}


class Solution {
public:
    bool prim(int x) {
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                cout << i << endl;
                return false;
            }
        }
        return true;
    }
    int smallestValue(int n) {
        memset(st, false, sizeof st);
        cnt = 0;

        getprim();

        // cout<<prim(n)<<endl;
        int ans = n;
        if (n == 4) {
            return 4;
        }
        while (st[ans]) {
            int k = 0;
            for (int i = 2; i <= ans / i; i++) {
                if (ans % i == 0) {
                    while (ans % i == 0) {
                        ans /= i;
                        k += i;
                    }
                }
            }
            if (ans > 1)k += ans;
            ans = k;
        }
        return ans;
    }
};